package work3;

/**
 * @author zhangxufeng@meitunmama.com 2019-08-28 10:56:21
 */
public class Solution {

  public int lengthOfLongestSubstring(String s) {
    if (null == s || s.length() == 0) {
      return 0;
    }

    int[] marker = initializeMarker();
    int start = 0, result = 0;
    int length = s.length();
    for (int i = start; i < length; i++) {
      char ch = s.charAt(i);
      int index = getIndex(ch);
      if (marker[index] == -1) {
        marker[index] = i;
        int tmp = i - start + 1;
        if (tmp > result) {
          result = tmp;
        }
      } else {
        // 重置前面的数据
        int tmpStart = marker[index] + 1;
        resetMarkerPartially(marker, s, start, marker[index]);

        // 将重复的字符标记为新的位置
        marker[index] = i;

        // 发现重复之后，如果新的长度比之前的长度要大，则记录该长度
        int tmp = i - start;
        if (tmp > result) {
          result = tmp;
        }

        // 将开始位置标记为发现重复字符的后面一位
        start = tmpStart;
      }
    }

    return result;
  }

  private void resetMarkerPartially(int[] marker, String s, int start, int end) {
    for (int i = start; i <= end; i++) {
      char ch = s.charAt(i);
      marker[getIndex(ch)] = -1;
    }
  }

  private int[] initializeMarker() {
    int[] result = new int[128];
    for (int i = 0; i < result.length; i++) {
      result[i] = -1;
    }

    return result;
  }

  private int getIndex(char ch) {
    return ch;
  }

}
